package DP;

/**
 * 718.最长重复子数组
 * 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 * dp[i][j]:以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]
 * 当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
 */
public class findLength {
    /**
     * 一刷二刷思路一致不做记录
     */
    //代表以i-1结尾
    public int findLength(int[] nums1, int[] nums2) {
        int result = 0;
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }
        return result;
    }


    //代表以i结尾
    public int myfindLength(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0)   return 0;
        int [][]dp = new int[nums1.length][nums2.length];
        int max=0;
        for (int i = 0; i < dp.length; i++) {
            if(nums1[i] == nums2[0]){
                dp[i][0] = 1;
                if(max < 1) max = 1;
            }
        }
        for (int j = 0; j < dp[0].length; j++) {
            if(nums1[0] == nums2[j]){
                dp[0][j] = 1;
                if(max < 1) max = 1;
            }
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if(nums1[i] == nums2[j])   dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = 0;
                if(dp[i][j] > max) max = dp[i][j];
            }
        }
        return max;
    }
}
